As a method of diagnosing deterioration of an exhaust gas purification apparatus disposed in an exhaust passage of an internal combustion engine, there has been known a method of using measured values of air fuel ratio sensors or oxygen concentration sensors which are disposed in a portion of the exhaust passage at the upstream side of the exhaust gas purification apparatus and in a portion of the exhaust passage at the downstream side of the exhaust gas purification apparatus, respectively. Specifically, there has been known a technology in which an amount of oxygen (O2), which can be stored by the exhaust gas purification apparatus (hereinafter, referred to as an “oxygen storage capacity”), is obtained from a difference between outputs of the above-mentioned sensors disposed at two locations (hereinafter, referred to as a “sensor output difference”) at the time of changing the air fuel ratio of the exhaust gas flowing into the exhaust gas purification apparatus from a lean air fuel ratio higher than a stoichiometric air fuel ratio into a rich air fuel ratio lower than the stoichiometric air fuel ratio, and the deterioration of the exhaust gas purification apparatus is diagnosed based on the oxygen storage capacity thus obtained (see, for example, patent literature 1). Further, in patent literature 2, there is disclosed a technology in which in an exhaust gas purification apparatus provided with a three-way catalyst and a lean NOx catalyst, the amount of a reducing agent to be supplied to the lean NOx catalyst is adjusted according to the deterioration degree of the three-way catalyst.